﻿class Solution
	2 {
3 public:
	4 int numDecodings(string s)
		5 {
		6 int n = s.size();
		7 vector<int> dp(n); // 创建⼀个 dp表
		8
			9 // 初始化前两个位置
			10 dp[0] = s[0] != '0';
		11 if (n == 1) return dp[0]; // 处理边界情况
		12
			13 if (s[1] <= '9' && s[1] >= '1') dp[1] += dp[0];
		14 int t = (s[0] - '0') * 10 + s[1] - '0';
		15 if (t >= 10 && t <= 26) dp[1] += 1;
		16
			17 // 填表
			18 for (int i = 2; i < n; i++)
			19 {
			20 // 如果单独编码
				21 if (s[i] <= '9' && s[i] >= '1') dp[i] += dp[i - 1];
			22 // 如果和前⾯的⼀个数联合起来编码
				23 int t = (s[i - 1] - '0') * 10 + s[i] - '0';
			24 if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
			25 }
		26
			27 // 返回结果
			28 return dp[n - 1];
		29 }
	30 };